Upon rasterizing print data output from an application program which arranges and outputs identical background patterns called a wallpaper or texture and printing the image data, when this image data is compressed to reduce its data size, it is easy to compress the entire image data if the background pattern itself can be compressed well. However, the background pattern itself cannot often be compressed well, and it is not easy in such case to compress the entire image data well.
FIG. 10 shows an example of such print data, in which the background is formed by arranging identical patterns, as shown in FIG. 11.
As conventional compression techniques, an encoding method such as runlength or delta-law coding which refers to neighboring pixels using strong tendency that a pixel value has the same value as neighboring pixels, and compresses these pixels if they have identical values is known.
Also, an encoding method such as LZ77 coding or LZ78 coding that refers to pixels within a broad range to detect a pixel sequence having identical values, and compresses data by utilizing such pixel sequence is available. According to these methods, since pixels which are located at considerably distant positions and have identical values can be detected and used in compression, the aforementioned wallpaper can be compressed well.
Also, an encoding method such as JPEG coding, which can compress a background pattern itself well, is known.
Japanese Patent Application No. 2000-76424 discloses a compression method by detecting the period of a texture.
However, according to the runlength or delta-law coding, when the aforementioned wallpaper or the like is compressed, since its repetition period assumes a value as large as, e.g., 1024 pixels, the wallpaper or the like cannot be compressed well if only neighboring pixels are referred to.
According to LZ77 or LZ78 coding, since pixels within a broad range must be referred to upon encoding, the computation volume is large, and the time required to encode is long. According to these methods, since pixels within a broad range must be referred to upon decoding, a large-size buffer memory is required, and such methods cause an increase in cost, when a decoding function is provided to a printer.
According to JPEG, since the computation volume upon encoding is large, the time required to encode is long. Also, according to this method, the computation volume upon decoding is also large, and this method causes an increase in cost when a decoding function is provided to a printer.
According to Japanese Patent Application No. 2000-76424, since a huge volume of computations are required using background pattern data since it is based on Fourier analysis or autocorrelation function, it is impossible to achieve high-speed encoding.
The present invention has been made in consideration of the aforementioned problems, and has as its object to compress the entire image at a high speed and high compression ratio upon encoding an image having periodicity, especially, image data formed by arranging identical background patterns such as a wallpaper or the like.
It is another object of the present invention to reduce the circuit scale of a decoding circuit that decodes codes obtained by encoding an image formed by arranging identical background patterns such as a wallpaper or the like, and to implement low-cost decoding without requiring any large-size buffer memory.
In a method of compressing data, when data of interest matches a previous data sequence, the runlength of the same data is encoded; otherwise, the data itself is encoded.
For example, in LZ77 compression, when data of interest matches a data sequence at an arbitrary position within a moving window of a predetermined size, the position of that data sequence and the runlength of the same data are encoded; otherwise, the data itself is encoded.
On the other hand, upon compressing image data, the following method is known. That is, when data of interest matches data at one or a plurality of predetermined positions, e.g., a data sequence at an upper or left position of the data to be encoded, the runlength of the same data is encoded; otherwise, the data itself is encoded.
On the other hand, a method disclosed in Japanese Patent Laid-Open No. 6-242924 is known. In this method, data which appears latest is stored in a cache buffer, and if a cache hit has occurred, an index where the data that matches is stored is encoded, thus encoding data to a shorter code than that obtained by encoding data itself.
However, in the above method, when the frequency of occurrence of matching of data sequences is low, many codes are obtained by encoding data themselves, and the compression ratio drops considerably.
On the other hand, in the method disclosed in Japanese Patent Laid-Open No. 6-242924, even when data of interest matches a previous data sequence, that redundancy cannot be used in compression, and it is difficult to obtain a high compression ratio.
The present invention has been made in consideration of the aforementioned problems, and has as its object to obtain a high compression ratio-by utilizing redundancy if data of interest matches a previous data sequence, and can minimize any compression ratio drop even when the frequency of occurrence of matching of data sequences is low.
Upon rasterizing print data output from an application program which arranges and outputs identical background patterns called a wallpaper or texture and printing the image data, when this image data is compressed to reduce its data size, it is easy to compress the entire image data if the background pattern itself can be compressed well.
However, the background pattern itself cannot often be compressed well, and it is not easy in such case to compress the entire image data well. FIG. 10 shows an example of such print data. According to the prior art, image data of a text part can be compressed well, but image data of a background pattern cannot be compressed well since it has an irregular pattern and has low correlation with neighboring image data. Since the background pattern normally has a broad area, and one page has a large proportion of the background pattern, if the background pattern cannot be compressed well, the entire page cannot be compressed well, either.
The present invention has been made in consideration of the aforementioned problems, and has as its object to provide an image processing method that includes an encoding method which can compress image data having a background pattern well, even when the background pattern has low correlation with neighboring pixel data, and a decoding method which decodes codes obtained by that encoding method.
Conventionally, upon compressing image data, by utilizing the tendency that pixels having identical pixel values successively appear in the horizontal and vertical directions, it is a common practice to encode data with reference to a pixel at a left or upper neighboring position having high correlation with the position of interest.
On the other hand, when image data to be compressed has undergone a color reduction process using a dither matrix, since neighboring pixels undergo different arithmetic operations in the color reduction process, a pixel of interest has higher correlation with pixels separated by the period of the dither matrix used in the color reduction process than neighboring pixels. Therefore, in such case, if the period of the dither matrix used in the color reduction process is known, encoding is done with reference to data at a left or upper position separated by the period of the dither matrix from the position of interest.
However, according to the above method, if the period of image data is different from that of the dither matrix, since the correlation between the position of interest and reference position is not so high, efficient compression is disturbed. For example, such problem is often posed when image data to be compressed has undergone the color reduction process after resolution conversion of an original image having a different resolution.
The present invention has been made in consideration of the aforementioned problems, and has as its object to efficiently encode an image using especially a short code.